package com.xk._02算法篇._07divideConquer;

/**
 * @description:
 * @author: xu
 * @date: 2022/10/17 22:08
 */
public class Main {
    public static void main(String[] args) {
        int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println(maxSubarray(nums));
    }

    /**
     * 分治解法
     * T(n) = 2T(n/2) + O(n) = O(nlogn)
     * @param nums
     * @return
     */
    static int maxSubarray(int[] nums){
        return maxSubarray(nums, 0, nums.length);
    }
    static int maxSubarray(int[] nums, int begin, int end){
        if (end - begin < 2) return nums[begin];
        int mid = (begin + end) >> 1;

        int leftMax = nums[mid - 1], sum = 0;
        for (int i = mid - 1; i >= begin; i--) {
            sum += nums[i];
            leftMax = Math.max(sum, leftMax);
        }

        sum = 0;
        int rightMax = nums[mid];
        for (int i = mid; i < end; i++) {
            sum += nums[i];
            rightMax = Math.max(sum, rightMax);
        }
        return Math.max(leftMax + rightMax,
                Math.max(maxSubarray(nums, begin, mid), maxSubarray(nums, mid, end)));
    }

    // 暴力解法 -- 优化
    static int maxSubarray2(int[] nums){
        if (nums == null || nums.length == 0) return 0;
        int max = Integer.MIN_VALUE;
        for (int begin = 0; begin < nums.length; begin++) {
            // sum 是 [begin, end] 的和
            int sum = 0;
            for (int end = begin; end < nums.length; end++) {
                sum += nums[end];
                max = Math.max(max, sum);
            }
        }
        return max;
    }

    // 暴力解法
    static int maxSubarray1(int[] nums){
        if (nums == null || nums.length == 0) return 0;
        int max = Integer.MIN_VALUE;
        for (int begin = 0; begin < nums.length; begin++) {
            for (int end = begin; end < nums.length; end++) {
                // sum 是 [begin, end] 的和
                int sum = 0;
                for (int i = begin; i <= end; i++) {
                    sum += nums[i];
                }
                max = Math.max(max, sum);
            }
        }
        return max;
    }
}
